#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <utility>
#include <cmath>
#include <stdexcept>

typedef unsigned VecIndex;
typedef float VecValue;
typedef std::pair<VecIndex, VecValue> VecPair;
typedef std::vector<VecPair> Vector;
typedef std::vector<Vector> Vectors;

void fill_vectors_from_file(Vectors &vectors, const std::string &file_name) {
    vectors.clear();
    std::ifstream in_file(file_name.c_str());
    if (!in_file) {
        throw std::runtime_error(file_name + " file open error");
    }
    VecIndex index;
    VecValue value;
    char delimiter;
    while (in_file) {
        std::string line;
        Vector vector;
        std::getline(in_file, line);
        if (!line.size()) break;
        std::istringstream ss(line);
        while (ss) {
            ss >> index;
            if (!ss) break;
            ss.get(delimiter);
            ss >> value;
            if (delimiter != ':') {
                std::string reason("delimiter error: " + delimiter);
                throw std::runtime_error(reason);
            }
            vector.push_back(std::make_pair(index, value));
        }
        if (vector.size()) {
            vectors.push_back(vector);
        }
    }
    in_file.close();
}

void fill_values_from_vectors(VecValue *values, const Vectors &vectors, VecIndex max_index) {
    for (Vectors::const_iterator iter_vectors(vectors.begin()); iter_vectors != vectors.end(); ++iter_vectors) {
        for (Vector::const_iterator iter_vector(iter_vectors->begin()); iter_vector != iter_vectors->end(); ++iter_vector) {
            values[iter_vector->first] += iter_vector->second;
        }
    }
    for (VecIndex index = 1; index <= max_index; ++index) {
        values[index] /= vectors.size();
    }
}

void normalize(Vector &vector) {
    double norm2 = 0;
    for (Vector::const_iterator iter(vector.begin()); iter != vector.end(); ++iter) {
        norm2 += iter->second * iter->second;
    }
    norm2 = std::sqrt(norm2);
    if (norm2 == 0) return;
    for (Vector::iterator iter(vector.begin()); iter != vector.end(); ++iter) {
        iter->second /= norm2;
    }
}

double get_similarity(const Vector &vec1, const Vector &vec2) {
    double similarity = 0;
    for (Vector::const_iterator iter1(vec1.begin()), iter2(vec2.begin()); iter1 != vec1.end() && iter2 != vec2.end();) {
        if (iter1->first == iter2->first) {
            similarity += iter1->second * iter2->second;
            ++iter1;
            ++iter2;
        }
        else if (iter1->first < iter2->first) {
            ++iter1;
        }
        else {
            ++iter2;
        }
    }
    return similarity;
}

VecIndex get_max_index(const Vectors &vectors) {
    VecIndex max_index = 0;
    for (Vectors::const_iterator iter(vectors.begin()); iter != vectors.end(); ++iter) {
        VecIndex index = ((*iter)[iter->size() -1]).first;
        if (index > max_index) max_index = index;
    }
    return max_index;
}

void get_center_vectors(const Vectors &pos_vectors, const Vectors &unlabeled_vectors, Vector &pos_center_vector, Vector &unlabeled_center_vector) {
    pos_center_vector.clear();
    unlabeled_center_vector.clear();

    VecIndex max_index1 = get_max_index(pos_vectors);
    VecIndex max_index2 = get_max_index(unlabeled_vectors);
    VecIndex max_index = max_index1 > max_index2 ? max_index1 : max_index2;

    VecValue *pos_values = new VecValue[max_index + 1](), *unlabeled_values = new VecValue[max_index + 1]();

    fill_values_from_vectors(pos_values, pos_vectors, max_index);
    fill_values_from_vectors(unlabeled_values, unlabeled_vectors, max_index);

    const int rocchio_alpha = 16, rocchio_beta = 4;
    for (VecIndex index = 1; index <= max_index; ++index) {
        if (pos_values[index] || unlabeled_values[index]) {
            pos_center_vector.push_back(std::make_pair(index, rocchio_alpha * pos_values[index] - rocchio_beta * unlabeled_values[index]));
            unlabeled_center_vector.push_back(std::make_pair(index, rocchio_alpha * unlabeled_values[index] - rocchio_beta * pos_values[index]));
        }
    }
    delete [] pos_values;
    delete [] unlabeled_values;
}

void print_vector_to_stream(const Vector &vector, std::ofstream &outfile_stream, const std::string &flag="0") {
    outfile_stream << flag << " ";
    for (Vector::const_iterator iter(vector.begin()); iter != vector.end(); ++iter) {
        outfile_stream << iter->first << ":" << iter->second << " ";
    }
    outfile_stream << std::endl;
}

void extract_reliable_negative_examples(const std::string &positive_file, const std::string &unlabeled_file, const std::string &problem_file, const std::string &test_file) {
    Vectors pos_vectors, unlabeled_vectors;

    std::cerr << "start reading in vectors...";
    fill_vectors_from_file(pos_vectors, positive_file);
    fill_vectors_from_file(unlabeled_vectors, unlabeled_file);
    std::cerr << "Done! positive: " << pos_vectors.size() << "; unlabeled: " << unlabeled_vectors.size() << std::endl;

    Vector pos_center_vector, unlabeled_center_vector;

    std::cerr << "calculating center vectors...";
    get_center_vectors(pos_vectors, unlabeled_vectors, pos_center_vector, unlabeled_center_vector);
    std::cerr << "Done!" << std::endl;
    
    std::ofstream svm_problem_stream(problem_file.c_str());
    for (Vectors::const_iterator iter(pos_vectors.begin()); iter != pos_vectors.end(); ++iter) {
        print_vector_to_stream(*iter, svm_problem_stream, "+1");
    }
    std::ofstream unlabeled_stream(test_file.c_str());

    std::cerr << "start extracting reliable negative examples..." << std::endl;
    unsigned reliable_negative_exmaples_cnt = 0;
    unsigned count = 0;
    for (Vectors::iterator iter(unlabeled_vectors.begin()); iter != unlabeled_vectors.end(); ++iter) {
        count++;
        if (count % 1000 == 0) {
            std::cerr << "Record: " << count << std::endl;
        }
        if (get_similarity(*iter, pos_center_vector) < get_similarity(*iter, unlabeled_center_vector)) {
            ++reliable_negative_exmaples_cnt;
            print_vector_to_stream(*iter, svm_problem_stream, "-1");
        }
        else {
            print_vector_to_stream(*iter, unlabeled_stream, "-1");
        }
    }
    svm_problem_stream.close();
    unlabeled_stream.close();
    std::cerr << "Done! " << reliable_negative_exmaples_cnt << " reliable negative examples extracted!" << std::endl; 
}

int main(int argc, char **argv) {
    if (argc < 5) {
        std::cerr << "Usage: " << argv[0] << " [positive_file] [unlabeled_file] [svm_learn] [svm_classify] [output_model_file]" << std::endl;
        exit(1);
    }

    std::string positive_file(argv[1]), unlabeled_file(argv[2]), svm_learn(argv[3]), svm_classify(argv[4]), output_model_file(argv[5]);

    extract_reliable_negative_examples(positive_file, unlabeled_file, "svm_problems", "unlabeled");
    
    unsigned round = 1;
    unsigned new_negative_examples_cnt;

    do {
        new_negative_examples_cnt = 0;
        std::cerr << "Round " << round++ << std::endl;
        std::string command = svm_learn + " svm_problems " + output_model_file; 
        system(command.c_str());
        command = svm_classify + " unlabeled " + output_model_file + " svm_predictions";
        system(command.c_str());
        std::ifstream svm_prediction_stream("svm_predictions");
        std::ifstream unlabeled_stream("unlabeled");
        std::ofstream svm_problem_stream("svm_problems", std::ofstream::app);
        std::ofstream tmp_stream("tmp");
        double value;
        while (svm_prediction_stream) {
            std::string line;
            std::getline(unlabeled_stream, line);
            svm_prediction_stream >> value;
            if (!svm_prediction_stream) break;
            if (value > 0) {
                tmp_stream << line << std::endl;
            }
            else {
                svm_problem_stream << line << std::endl;
                ++new_negative_examples_cnt;
            }
        }
        std::cerr << new_negative_examples_cnt << " new negative examples found!" << std::endl;
        svm_prediction_stream.close();
        unlabeled_stream.close();
        svm_problem_stream.close();
        tmp_stream.close();
        system("rm unlabeled");
        system("mv tmp unlabeled");
    } while (new_negative_examples_cnt > 0);
    system("rm unlabeled svm_predictions svm_problems");
    return 0;
}
